Mining Time Series Motifs with Probabilistic Guarantees

Matteo Ceccarello

University of Padova

Joint work with Johann Gamper (U. Bolzano)

Outline

  1. Problem definition
  2. State of the art
  3. Locality Sensitive Hashing
  4. Our algorithm
  5. Experimental results

Motivation

Subsequences

Fix a subsequence length \(w\)

  • The Euclidean distance measures the similarity between subsequences
  • Subsequences can be seen as points in a \(w\) dimensional space

Top-\(k\) motifs

Top-\(k\) motifs

Consider all pairs of (non-overlapping) subsequences of length \(w\) of a given time series. The first \(k\) by increasing distance are the top-\(k\) motifs.

State of the art: Matrix Profile

State of the art: Matrix Profile

  • For each subsequence, find the nearest neighbor
  • Find the pair at minimum distance
  • Leverage the fact that consecutive subsequences share a lot of structure
  • Parallelize with many GPUs

  • Still, it’s a \(\Omega(n^2)\) algorithm

  • Finds motifs out of 1 billion long time series in one day, using 5 GPUs

Goal

  • Find the top motifs without computing all-pairs-distances
  • We need an index

Challenges

  • Subsequences can be seen as vectors
  • These vectors are high dimensional
  • Curse of dimensionality: indices such as R-trees degrade to linear scans

To address these challenges, we will use an approach based on Locality Sensitive Hashing (LSH)

We consider the z-normalized Euclidean distance \[ d(x, y) = \sqrt{\sum_{i\in[1,w]} \left( \frac{x_i - \bar{x}}{\sigma_x} - \frac{y_i - \bar{y}}{\sigma_y} \right)^2 } \] In this example we have a window length \(w = 640\),
hence we have vectors in \(\mathbb{R}^{640}\)

Locality Sensitive Hash function:

  • choose \(r \in \mathbb{R}^+\)
  • sample \(\vec{a} \sim \mathcal{N}(0,1)^w\), \(b \sim \mathcal{U}(0,r)\)

\[ h(\vec{x}) = \left\lfloor\frac{\vec{a} \cdot \vec{x} + b}{r}\right\rfloor \]

The key point is that we only compute the distance of subsequences falling
into the same bucket.

To lower the collision probability we concatenate \(k\) hash functions \[ \hat{h}(\vec{x}) = \langle h_1(\vec{x}), \dots, h_k(\vec{x}) \rangle \] this makes for a better precision of the index.

And to increase the recall of the index we repeat \(L\) times.

A simple algorithm

  1. Build a priority queue to hold candidate motifs

  2. Fix \(K\)

  3. Repeat:

  4. Sample \(K\) hash functions, hash all the points, and compute the distances of pairs in the same bucket

  5. Let \(d_k\) be the distance of the \(k\)-th motif

  6. If the probability of having seen all pairs
    at distance \(\ge d_k\) is at least \(1-\delta\),
    then return.

Dealing with parameters

  • How to fix \(K\)?
  • The wrong choice could force us to run too many repetitions
  • We adopt an approach that auto-tunes parameters based on the data

  • \(L_{max}\) maximum number of repetitions,
  • \(K_{max}\) maximum number of concatenations (e.g. 4).

Repetition 1

Repetition 2

In each iteration we compute the distance of all subsequences in the same bucket.

In the first iteration, with \(k=4\), we discover a pair at distance 2
.

After 10 repetitions, we find a pair at distance 1
.

After 100 repetitions we did not find a better pair,
and the success probability is about 0.85

We then consider shorter prefixes of the hashes,
going through the 100 repetitions again.

After 15 repetitions, we observe that the
success probability is above our target, and thus return.

Complexity

Theorem 1 The LSH index construction takes time \[ O(K_{max} \cdot \sqrt{L_{max}} n\log n) \]

Theorem 2 Let \(d(m_k)\) be the distance of the \(k\)-th motif, and \(i'\le K\), \(j' \le L\) be the parameters used by the optimal LSH algorithm. Then, the algorithm considers \[ O\left( j'\sum_{m\in T^w\times T^w} p(d(m))^{i'} + (L-j')\sum_{m\in T^w\times T^w} p(d(m))^{i'+1} \right) \] pairs in expectation.

Optimizations

  • Use a trie data-structure to re-use computations across iterations at different \(k\) values
  • Compute dot producs for hash values in the frequency domain (also done in some implementations of the Matrix Profile)
  • Compute fewer hash values using tensoring

Experimental results

Find the top-10 motifs.

dataset \(n\) (millions) RC
astro 1 8.63
GAP 2 9.17
freezer 7 7.95
ECG 7 109.06
HumanY 26 581.03
Whales 308 21.66
Seismic 1000 274.44

Relative Contrast measures difficulty: higher is easier. \[ RC = \frac{d_{avg}}{d_{m_k}} \]

Scalability

Synthetic data, planted motifs with different relative contrasts. SCAMP-gpu only has one line since it is data-independent.

Practical takeaways

  • For shorter time series, or if the relative contrast is very small, use the Matrix Profile.

  • For time series of a few million values and above, with a not-to-small relative contrast, try Attimo

References

  • Matteo Ceccarello, Johann Gamper: Fast and Scalable Mining of Time Series Motifs with Probabilistic Guarantees. Proc. VLDB Endow. 15(13): 3841-3853 (2022)

https://github.com/Cecca/attimo



import pyattimo
ts = pyattimo.load_dataset("ecg", prefix=1000000)
motifs = pyattimo.MotifsIterator(
    ts, 
    w=1000
)
m = next(motifs)
print(m)
motif: (723776, 796052) d=0.4335137534580184
matteo.ceccarello@unipd.it

Appendix

Influence of the maximum number of repetitions

Running for top-10 motifs, for different number of repetitions.

Difficult datasets

Data from LIGO:

  • Length 100k, window 1k
  • Top motif distance \(\approx 40\)
  • Average distance \(\approx 44\)
  • Relative contrast \(\approx 1.1\)
  • Attimo: 6 hours
  • SCAMP: \(\approx 1\) second

freezer and the 7-th motif

7M points, window 5000

  • In black are the distances of the top-10 motifs extracted from the matrix profile.
  • In red the distance of a pair of subsequences neither of which is the nearest neighbor of the other, and not overlapping with higher-ranked motifs.
  • The matrix profile holds the distances and indices of the 1-nearest neighbor of each subsequence, but top-k motifs would require the k-nearest neighbors to be maintained in the matrix profile.

Top-k and k-NN

  • Solid lines are nearest neighbor distances
  • The dashed line is the distance of the top-2 pair in the definition we are using
  • The Matrix Profile contains information about 1-nearest neighbors (solid black lines)